<!DOCTYPE html>
<html lang="en">
	<head>
		<meta charset="UTF-8" />
		<meta name="viewport" content="width=device-width, initial-scale=1.0" />
		<meta http-equiv="X-UA-Compatible" content="ie=edge" />
		<title>JavaScript 数据结构与算法之美 - 桶排序</title>
	</head>
	<body></body>
	<script>
		// 桶排序
		const bucketSort = (array, bucketSize) => {
			if (array.length === 0) {
				return array;
			}

			console.time('桶排序耗时');
			let i = 0;
			let minValue = array[0];
			let maxValue = array[0];
			for (i = 1; i < array.length; i++) {
				if (array[i] < minValue) {
					minValue = array[i]; //输入数据的最小值
				} else if (array[i] > maxValue) {
					maxValue = array[i]; //输入数据的最大值
				}
			}

			//桶的初始化
			const DEFAULT_BUCKET_SIZE = 5; //设置桶的默认数量为 5
			bucketSize = bucketSize || DEFAULT_BUCKET_SIZE;
			const bucketCount = Math.floor((maxValue - minValue) / bucketSize) + 1;
			const buckets = new Array(bucketCount);
			for (i = 0; i < buckets.length; i++) {
				buckets[i] = [];
			}

			//利用映射函数将数据分配到各个桶中
			for (i = 0; i < array.length; i++) {
				buckets[Math.floor((array[i] - minValue) / bucketSize)].push(array[i]);
			}

			array.length = 0;
			for (i = 0; i < buckets.length; i++) {
				// insertionSort(buckets[i]); //对每个桶进行排序，这里使用了插入排序
				quickSort(buckets[i]); //对每个桶进行排序，这里使用了快速排序
				for (var j = 0; j < buckets[i].length; j++) {
					array.push(buckets[i][j]);
				}
			}
			console.timeEnd('桶排序耗时');

			return array;
		};

		// 快速排序
		const quickSort = (arr, left, right) => {
			let len = arr.length,
				partitionIndex;
			left = typeof left != 'number' ? 0 : left;
			right = typeof right != 'number' ? len - 1 : right;

			if (left < right) {
				partitionIndex = partition(arr, left, right);
				quickSort(arr, left, partitionIndex - 1);
				quickSort(arr, partitionIndex + 1, right);
			}
			return arr;
		};

		const partition = (arr, left, right) => {
			//分区操作
			let pivot = left, //设定基准值（pivot）
				index = pivot + 1;
			for (let i = index; i <= right; i++) {
				if (arr[i] < arr[pivot]) {
					swap(arr, i, index);
					index++;
				}
			}
			swap(arr, pivot, index - 1);
			return index - 1;
		};

		const swap = (arr, i, j) => {
			let temp = arr[i];
			arr[i] = arr[j];
			arr[j] = temp;
		};

		// 插入排序
		const insertionSort = array => {
			const len = array.length;
			if (len <= 1) return;

			let preIndex, current;
			for (let i = 1; i < len; i++) {
				preIndex = i - 1; //待比较元素的下标
				current = array[i]; //当前元素
				while (preIndex >= 0 && array[preIndex] > current) {
					//前置条件之一: 待比较元素比当前元素大
					array[preIndex + 1] = array[preIndex]; //将待比较元素后移一位
					preIndex--; //游标前移一位
				}
				if (preIndex + 1 != i) {
					//避免同一个元素赋值给自身
					array[preIndex + 1] = current; //将当前元素插入预留空位
					// console.log('array :', array);
				}
			}
			return array;
		};

		// 测试
		const array = [4, 6, 8, 5, 9, 1, 2, 5, 3, 2];
		console.log('原始array:', array);
		const newArr = bucketSort(array);
		console.log('newArr:', newArr);
		// 原始 array:  [4, 6, 8, 5, 9, 1, 2, 5, 3, 2]
		// 堆排序耗时:   0.133056640625ms
		// newArr:  	 [1, 2, 2, 3, 4, 5, 5, 6, 8, 9]
	</script>
</html>
